package com.example.algorithm.union_find;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 并查集应用
 * 力扣每日一题的，没做出来
 */
public class UnionFindTest {

    private int[] parent;

    public static void main(String[] args) {
        int[][] roads = {
                {1, 2, 9},
                {2, 3, 6},
                {2, 4, 5},
                {1, 4, 7}
        };
        System.out.println(new UnionFindTest().minScore(4, roads));
    }

    public int minScore(int n, int[][] roads) {
        int min = Integer.MAX_VALUE;
        List<int[]>[] e = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            e[i] = new ArrayList<>();
        }
        for (int[] r : roads) {
            e[r[0]].add(new int[]{r[1], r[2]});
            e[r[1]].add(new int[]{r[0], r[2]});
        }
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        for (int[] r : roads) {
            union(r[0], r[1]);
        }
        for (int i = 1; i <= n; i++) {
            if (find(i) == 1 && !e[i].isEmpty()) {
                e[i].sort(Comparator.comparingInt(a -> a[1]));
                min = Math.min(min, e[i].get(0)[1]);
            }
        }
        return min;
    }

    public int find(int x) {
        while (x != parent[x]) {
            x = parent[x];
            parent[x] = parent[parent[x]];
        }
        return x;
    }

    public void union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX <= rootY) {
            parent[rootY] = rootX;
        } else {
            parent[rootX] = rootY;
        }
    }
}
